home *** CD-ROM | disk | FTP | other *** search
/ Monster Media 1996 #15 / Monster Media Number 15 (Monster Media)(July 1996).ISO / prog_c / cuj0696.zip / DWYER.ZIP / GAP.TST / GAPCOD.TXT < prev    next >
Text File  |  1996-02-12  |  2KB  |  56 lines
  1. PSEUDO CODE FOR KOLMOGOROV-SMIRNOV TEST IN GAP TEST
  2.  
  3. This algorithm calculates Kolmogorov-Smirnov statistics and
  4. probabilities for a set of gap lengths specified by the user.
  5. First, 100 chi-square probabilities are calculated and stored.
  6. These probabilities are used to calculate Kolmogorov-Smirnov
  7. statistics and probabilities and the results are printed.  This
  8. algorithm is largely due to D.E. Knuth [K1, pp. 60-61].
  9.  
  10. Inputs:
  11.  
  12. C = Number of Categories  (= G+1)
  13. E = Array of Cell Expectations, One for Each Category
  14. L = Lower Bound of Gap, 0 <= L <= H <= 1
  15. H = Higher Bound of Gap
  16. G = Maximum Gap Length to be Tabulated
  17. N = Number of Gaps to be Tabulated
  18. U() = Uniform Random Number Generator Function Under Test
  19.  
  20.  G1. [Initialize.]  Set F <- C-1. (This is the number of degrees
  21.      of freedom which serves as input to chdtr(), the chi-square
  22.      probability distribution function.)
  23.  
  24.  G2. [Generate Data for KS test.]  Set t <- 1.  (We will execute
  25.      steps G3 to G12 100 times, then go on to G13.)
  26.  
  27.  G3. [Calculate next chi-square statistic.]  Set k <- 0, SoS <- 0,
  28.      ChiSq <- -N, and set Count[i] <- 0, 1 <= i <= C.
  29.  
  30.  G4. [Initialize gap counter.]  Set g <- 0.
  31.  
  32.  G5. [Check for Gap.]  Set N <- U(). If L <= N <= H, a gap of length
  33.      g has been found; go to step G7.
  34.  
  35.  G6. [Increment k.]  Increase g by 1, go back to step G5.
  36.  
  37.  G7. [Tally gap length.]  If g > G, set g <- G. Increase Count[g] by 1.
  38.  
  39.  G8. [Test end.]  Increase k by 1. If k < N, go back to step G4.
  40.      Otherwise, a complete set of gaps has been tabulated.
  41.      Go to step G9.
  42.  
  43.  G9. [Calculate sum of squares.]  SoS <- SoS + Count[j], 1 <= j <= G.
  44. G10. [Finish chi-square statistic.]  ChiSq <- ChiSq + Count[j]^2 / E[j],
  45.      1 <= j <= C.
  46.  
  47. G11. [Calculate p-value.]  XsqProb[t] <- chdtr(F, ChiSq).
  48.  
  49. G12. [Test end.]  Increase t by 1.  If t <= 100, go back to step G3.
  50.  
  51. G13. [Calculate K-S data.]  Execute function KSCalc() to get K-S
  52.      statistics and probabilities.  There will be four quantities
  53.      produced - Kn+, Pn+, Kn-, Pn-.
  54.  
  55. G14. [Print Results.]  Print Kn+, Pn+, Kn-, Pn-.
  56.